package oop.ex1.dataStructures;

public class ArrayPriorityQueue extends AbstractPriorityQueue {

	public ArrayPriorityQueue(){
		_queue = new ComparableObject [DEFAULT_INITIAL_CAPACITY];
		_size=DEFAULT_STARTING_LOCATION;
	}
	
	///////////////////////////////////////////////////////
	//////////////Priority Queue Implementation////////////
	///////////////////////////////////////////////////////
	
	private void max_heapify(int index) {
		int largest;
		int left = findLeft(index);
		int right = findRight(index);
		if(left <= _size) {
			if(right > _size) {
				right = _size;
			}
			if(_queue[left].compare(_queue[index]) > 0) {
				largest = left;
			} else {
				largest = index;
			}
			if(_queue[right].compare(_queue[largest]) > 0) {
				largest = right;
			}
			if(largest!=index) {
				swapComparableObject(largest,index);
				max_heapify(largest);
			}
		}
	}
	
	private void increase_key(int index, ComparableObject key) {
		if(index<_size) {
			if( key.compare(_queue[index])<0 ) {
				return;
			}
		}
		_queue[index] = key;
		while(index>0 && _queue[index/2].compare(_queue[index])<0 ) {
			swapComparableObject(index,index/2);
			index = index/2;
		}
	}
	
	private int findLeft(int index) {
		index++;
		return(index*2-1);
	}

	private int findRight(int index) {
		index++;
		return(index*2);
	}


	private void swapComparableObject(int obj1,int obj2) {
		ComparableObject _tmpObject = _queue[obj1];
		_queue[obj1] = _queue[obj2];
		_queue[obj2] = _tmpObject;

	}
	
	///////////////////////////////////////////////////////
	////////////////Interface Implementation///////////////
	///////////////////////////////////////////////////////
	
	public void push(ComparableObject obj) {
		_size++;
		if(_size==_queue.length) {
			_queue = extendQueue(_queue, 2*_queue.length);
		}
		increase_key(_size,obj);
	}
	
	public ComparableObject poll() throws EmptyQueueException {
		if(_size==-1) {
			throw new EmptyQueueException();
		}
		ComparableObject maxComparableObject = _queue[0];
		_queue[0]=_queue[_size];
		_size--;
		max_heapify(0);
		return maxComparableObject;
	}
	
	public ComparableObject peek() throws EmptyQueueException {
		if(_size==-1) {
			throw new EmptyQueueException();
		}
		return _queue[0];
	}
	
	public void updatePriority(ComparableObject obj) throws ObjectNotFoundException {
		int objectLocation = findObjectLocation(obj);
		if(objectLocation<0) {
			throw new ObjectNotFoundException();
		}
		increase_key(objectLocation, obj);
	}
	
	
	///////////////////////////////////////////////////////
	//////////////////Custom Implementation////////////////
	///////////////////////////////////////////////////////
	
	public boolean isObjectInQueue(ComparableObject obj) {
		if(this.findObjectLocation(obj)==-1) return false;
		return true;
	}
	
	private int findObjectLocation(ComparableObject obj) {
		for(int i=0;i<=_size;i++) {
			if(obj==_queue[i]) {
				return i;
			}
		}
		return -1;
	}
	
	public void increase_object(ComparableObject obj) {
		increase_key(findObjectLocation(obj), obj);
	}
	
	public void maxheapify_object(ComparableObject obj) {
		max_heapify(findObjectLocation(obj));
	}
	
}
